import Data.Ord

sqrtContinuedFraction :: Integer -> [Integer]
sqrtContinuedFraction n = [ a_i | ( _ , _ , a_i) <- mdas ]
	where 
		mdas = iterate getNextTriplet (m_0, d_0, a_0)
		
		m_0 = 0
		d_0 = 1
		a_0 = (truncate.sqrt.fromIntegral) n
		
		getNextTriplet (m_i, d_i, a_i) = (m_j, d_j, a_j)
			where
				m_j = d_i * a_i - m_i 
				d_j = n - m_j*m_j `div` d_i 
				a_j = (a_0 + m_j) `div` d_j
				
getConvergents :: [Integer] -> [(Integer,Integer)]
getConvergents (a_0 : a_1 : as ) = pqs where 
	pqs = (a_0, 1) : (p_1, a_1) : zipWith3 getNextConvergent pqs (tail pqs) as
	p_1 = a_1 * a_0 + 1
	
	getNextConvergent (p_i, q_i) (p_j, q_j) a_k = (a_k * p_j + p_i, a_k * q_j + q_i)

numberOfDigits :: Integer -> Int
numberOfDigits = (length.show)

euler_057 = length $ filter (\(x,y) -> (comparing numberOfDigits x y) == GT ) $ take 1000 $ getConvergents $ sqrtContinuedFraction 2
	
			

